<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0044)http://www.ut.ee/boi/?item=boi.tasks.2.lamps -->
<HTML><HEAD><TITLE>BOI 2003</TITLE>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-15">
<STYLE type=text/css>BODY {
	BACKGROUND: #fff; COLOR: #000
}
A {
	BACKGROUND: #fff; COLOR: #833
}
.title1 {
	BACKGROUND: #fff; COLOR: #833
}
.title2 {
	BACKGROUND: #aaa; COLOR: #fff
}
.menu {
	BACKGROUND: #487; COLOR: #fff
}
.menu-here {
	BACKGROUND: #487; COLOR: #ff0
}
BODY {
	FONT-FAMILY: sans-serif
}
TD {
	FONT-FAMILY: sans-serif
}
A {
	FONT-WEIGHT: bold
}
.menu {
	
}
.title1 {
	FONT-WEIGHT: bold; FONT-SIZE: 200%
}
.title2 {
	FONT-WEIGHT: bold; FONT-SIZE: 150%
}
.sample {
	FONT-FAMILY: monospace
}
.math {
	FONT-STYLE: italic
}
BODY {
	VERTICAL-ALIGN: top
}
TD {
	VERTICAL-ALIGN: top
}
.title1 {
	VERTICAL-ALIGN: middle; TEXT-ALIGN: right
}
.title2 {
	VERTICAL-ALIGN: middle; TEXT-ALIGN: right
}
</STYLE>
      <H1>Lamps</H1>
      <P>There is a castle with a circular main hall. There are <SPAN 
      class=math>N</SPAN> lamps numbered from <SPAN class=math>1</SPAN> to <SPAN 
      class=math>N</SPAN> on the wall of the hall. Each of the lamps can be 
      either on or off. At each second the lamp number <SPAN class=math>i</SPAN> 
      changes its state if the lamp number <SPAN class=math>i+1</SPAN> is on, 
      except the lamp number <SPAN class=math>N</SPAN> changes its state if the 
      lamp number <SPAN class=math>1</SPAN> is on.</P>
      <P>Your task is, given the initial states of all lamps at some moment, to 
      find their states after <SPAN class=math>M</SPAN> seconds.</P>
      <H2>Input data</H2>
      <P>The first line of the input file <SPAN class=sample>LAMPS.IN</SPAN> 
      contains two integers <SPAN class=math>N</SPAN> (<SPAN 
      class=math>0&nbsp;&lt;&nbsp;N&nbsp;&#8804;&nbsp;10<SUP>6</SUP></SPAN>) and <SPAN 
      class=math>M</SPAN> (<SPAN 
      class=math>0&nbsp;&#8804;&nbsp;M&nbsp;&#8804;&nbsp;10<SUP>9</SUP></SPAN>). The next 
      <SPAN class=math>N</SPAN> lines contain the initial states of the lamps, 
      starting with the lamp number <SPAN class=math>1</SPAN>. A line containing 
      <SPAN class=sample>0</SPAN> means that the lamp is off and <SPAN 
      class=sample>1</SPAN> means that the lamp is on.</P>
      <H2>Output data</H2>
      <P>The output file <SPAN class=sample>LAMPS.OUT</SPAN> must contain 
      exactly <SPAN class=math>N</SPAN> lines describing the states of the lamps 
      after <SPAN class=math>M</SPAN> seconds, starting with the lamp number 
      <SPAN class=math>1</SPAN>.</P>
      <H2>Sample</H2>
      <TABLE>
        <TBODY>
        <TR>
          <TD class=sample>LAMPS.IN </TD>
          <TD class=sample>LAMPS.OUT </TD></TR>
        <TR>
          <TD class=sample>3 1<BR>0<BR>0<BR>1<BR></TD>
          <TD 
class=sample>0<BR>1<BR>1<BR></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></FONT><!-- end browsable version --></BODY></HTML>
